package Hot100;

import LinkedList.ListNode;

import java.util.HashMap;
import java.util.Map;

public class 随机链表的复制 {

    Map<ListNode, ListNode> cachedListNode = new HashMap<>();

    public ListNode copyRandomList(ListNode head) {
        /* 回溯 + 哈希表 */
        if (head == null) return null;
        if (!cachedListNode.containsKey(head)) {
            ListNode headNew = new ListNode(head.val);
            cachedListNode.put(head, headNew);
            headNew.next = copyRandomList(head.next);
            headNew.random = copyRandomList(head.random);
        }
        return cachedListNode.get(head);

        /* 迭代 + 节点拆分 */
        /*if (head == null) return null;
        ListNode cur = head;
        while (cur != null) {
            ListNode node = new ListNode(cur.val);
            node.next = cur.next;
            cur.next = node;
            cur = node.next;
        }
        cur = head;
        while (cur != null) {
            cur.next.random = cur.random != null ? cur.random.next : null;
            cur = cur.next.next;
        }
        cur = head;
        ListNode copy = head.next;
        ListNode cHead = copy;
        while (cur != null) {
            cur.next = copy.next;
            cur = cur.next;
            if (cur != null) copy.next = cur.next;
            copy = copy.next;
        }
        return cHead;*/
    }
}
